program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  arr: array of integer;
  n, i, t, m, num, r, x, a, b: integer;

begin
  readln (n);
  setlength (arr, n);
  randomize;
  for i := 0 to n - 1 do
    arr[i]:= -1;
  for i := 0 to n - 1 do
  begin
    repeat
      r:= random (n);
    until (arr[r]=-1);
    arr[r]:= i+1;
  end;
  for i := 0 to n - 1 do
    write (arr[i], ' ');
  writeln;

  for i := n-1 downto 0 do
  begin
    num:= i;
    while (1=1) do
    begin
      x:= arr[num];
      a:= 2000000;
      b:= a;
      if (2*num+1<n) then
        a:= 2*num+1;
      if (2*num<n) then
        b:= 2*num;
      if (a<=b) and (a<=x) then
      begin
        arr[num]:= a;
        arr[2*num+1]:= x;
        num:= 2*num+1;
      end else
      if (b<=a) and (b<=x) then
      begin
        arr[num]:= b;
        arr[2*num]:= x;
        num:= 2*num;
      end else
      if (x<=a) and (x<=b) then
        break;
    end;
  end;

  for i := 0 to n - 1 do
    write (arr[i], ' ');
  writeln;

  m:= n;
  for i := 0 to n - 1 do
  begin
    t:= arr[0];
    arr[0]:= arr[m-1];
    arr[m-1]:= t;
    dec (m);
    num:= 0;
    while (1=1) do
    begin
      x:= arr[num];
      a:= 2000000;
      b:= a;
      if (2*num+1<n) then
        a:= 2*num+1;
      if (2*num<n) then
        b:= 2*num;
      if (a<=b) and (a<=x) then
      begin
        arr[num]:= a;
        arr[2*num+1]:= x;
        num:= 2*num+1;
      end else
      if (b<=a) and (b<=x) then
      begin
        arr[num]:= b;
        arr[2*num]:= x;
        num:= 2*num;
      end else
      if (x<=a) and (x<=b) then
        break;
    end;
  end;

  for i := 0 to n - 1 do
    write (arr[i], ' ');
  readln;

end.
